10831. Пирог Жоры

Жора на праздник пригласил гостей. p из них прибыли вовремя, а a задержались. Известно, что p – простое число. Жора разрезал квадратный торт на квадратные кусочки одинаковой величины. Известно, что по одному кусочку торта Жора оставил для опоздавших гостей, а остальные поровну поделил среди тех, кто прибыл вовремя. Себе кусочка он не оставил. Мог ли таким образом Жора поделить торт для заданных a и p?

Вход. Каждая строка содержит два знаковых 32 - битных числа a и p. При этом a неотрицательно, p положительно. Последний тест содержит a = p = -1 и не обрабатывается.

Выход. Для каждого теста вывести в отдельной строке Yes, если указанное деление торта возможно и No в противном случае.

Пример входа

1 3
1024 17
2 101
0 1
-1 -1

Пример выхода

Yes

Yes

No

Yes

РЕШЕНИЕ

теория чисел - квадратические вычеты

Анализ алгоритма

Пусть торт было разрезано на n² частей. Обозначим через k количество кусочков торта, которое досталось p гостям. Тогда a + kp = n², откуда n² º a (mod p). Последнее уравнение имеет решение тогда и только тогда, когда число a есть квадратическим вычетом по простому модулю p. То есть символ Лежандра равен 1.

Критерий Эйлера. Число a, которое не делится на непарное простое p, является квадратическим вычетом по модулю p тогда и только тогда, когда º 1 (mod p), и квадратическим невычетом, если º -1 (mod p).

Из критерия Эйлера следует, что = = 1, = 0. То есть числа 0 и 1 являются квадратическими вычетами по любому простому модулю p. Если a º b (mod p), то = . Если входное значение a > p, то число a можно уменьшить, положив a = a mod p.

Для решения задачи достаточно вычислить символ Лежандра º (mod p). Если он равен 1, то вывести Yes, иначе No.

Пример

Для первого теста имеем уравнение n² º 1 (mod 3), которое имеет решение n = 1. Для третьего теста получим уравнение n² º 2 (mod 101), которое не имеет решений, так как = (mod 101) º 2⁵⁰ (mod 101) º -1.

Реализация алгоритма

Функция power вычисляет a^k mod n с временной оценкой O(log k). Поскольку в функции power следует умножать 32 - битовые числа, то во избежание потерь данных заведем 64 - битовые числа res и x.

int power(int a, int k, int n)

{

long long res = 1, x = a;

while(k > 0)

{

if (k & 1) res = res * x % n;

k >>= 1;

x = x * x % n;

}

return (int)res;

}

Читаем входные значения a и p. Положим a = a mod p (если этого не сделать – получим Time Limit). Если значение a равно 0 или 1 то ответ Yes, иначе по формуле вычисляем символ Лежандра. В соответствии с его значением выводим ответ.

while(scanf("%d %d",&a,&p) == 2, a + p > 0)

{

a = a % p;

if (!a || (a == 1)) res = 1;

else res = power(a,(p - 1) / 2,p);

if (res == 1) printf("Yes\n");

else printf("No\n");

}